#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int ans = 0;
        int64_t cur_max = 1;
        int pos = 0;
        while (cur_max <= n) {
            if (pos < nums.size() && cur_max >= nums[pos]) {
                cur_max += nums[pos++];
            } else {
                cur_max += cur_max;
                ans++;
            }
        }
        return ans;
    }
};